//
// Created by TianBo on 2022/5/31.
//

//经典动归，与前缀和相加比较大小，大就加，不大就用本身
//优化：空间优化，滚动数组

#include "iostream"
#include "vector"

using namespace std;

class Solution {
public:
    int maxSubArray2(vector<int>& nums) {
        vector<int> dp(nums.size());
        int res = nums[0];
        dp[0] = nums[0];

        for (int i = 1; i < nums.size(); ++i) {
            dp[i] = max(dp[i-1] + nums[i],nums[i]);
            res = max(res,dp[i]);
        }
        return res;
    }
    int maxSubArray(vector<int>& nums)
    {
        int dp1 = nums[0];
        int res = nums[0];

        for (int i = 1; i < nums.size(); ++i) {
            int dp2 = dp1;
            dp1 = max(dp2 + nums[i] , nums[i]);
            res = max(res,dp1);
        }
        return res;
    }
};

int main()
{
    vector<int> nums{-2,1,-3,4,-1,2,1,-5,4};
    Solution s;
    cout<<s.maxSubArray(nums)<<endl;
    return 0;
}